﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
//P1803 区间贪心问题 排序 以左端点为基准 新思路 得记
//const int N = 1e6 + 10;
//struct node
//{
//	int a;
//	int b;
//}t[N];
//int n;
//bool cmp(node& x, node& y)
//{
//	return x.a < y.a;
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> t[i].a >> t[i].b;
//	//根据左端点从小到大进行排序
//	sort(t + 1, t + 1 + n, cmp);
//	
//	int ret = 1;//默认取第一段
//	int r = t[1].b;
//	for (int i = 2; i <= n; i++)
//	{
//		int left = t[i].a, right = t[i].b;
//		if ( left < r)//存在重叠
//		{
//			r = min(r, right);
//		}
//		else
//		{
//			ret++; r = right;//不重叠 取该段作为基准
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}


//P1090 哈夫曼模板题 注意小堆细节
//priority_queue<int, vector<int>, greater<int>>heap;
//int n;
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		heap.push(x);
//	}
//	int ret = 0;
//	while (heap.size() > 1)
//	{
//		int x = heap.top(); heap.pop();
//		int y = heap.top(); heap.pop();
//		ret += x + y;
//		heap.push(x + y);
//	}
//	cout << ret << endl;
//	return 0;
//}

//NC233601 哈夫曼模板题
//const int N = 2e5 + 10;
//typedef long long int LL;
//priority_queue <LL, vector<LL>, greater<LL>> heap;//建小堆
//int n;
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		LL x; cin >> x;
//		heap.push(x);
//	}
//	long long int ret = 0;
//	while (heap.size()>1)
//	{
//		LL x = heap.top(); heap.pop();//每次取最小的两个数合并
//		LL y = heap.top(); heap.pop();
//		ret += x + y;//每合并一次 加上两个数的权值 实现哈夫曼权值相加
//		heap.push(x + y);//再将合并后的数值填入小堆
//	}
//	cout << ret << endl;
//	return 0;
//}
//P1842 推公式排序题 类似模板？
//const int N = 1e5 + 10;
//struct node
//{
//	int w;
//	int s;
//}a[N];
//int n;
//bool cmp(node& x, node& y)
//{
//
//	return max(-x.s, x.w - y.s) < max(-y.s, y.w - x.s);//如果x在前的站法 使得总压扁指数最小 就采用该站法 即x在y前
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i].w >> a[i].s;
//	sort(a + 1, a + 1 + n, cmp);
//	long long int ret = -1e9 - 10; long long int w = 0;//ret可能是负的 没考虑到这个问题
//	for (int i = 1; i <= n; i++)
//	{
//		ret = max(ret, w-a[i].s);
//		w += a[i].w;
//	}
//	cout << ret << endl;
//	return 0;
//}

//P2878 推公式排序 确定可以进行排序后 推出排序公式
//const int N = 1e5 + 10;
//struct node 
//{
//	int t;
//	int d;
//}a[N];
//int n;
//bool cmp(node& x, node& y)
//{
//	return x.t * y.d < y.t* x.d;//推公式所得
//}
//int main()
//{
//	cin >> n;
//	int d_sum = 0;
//	for (int i = 1; i <= n; i++)cin >> a[i].t >> a[i].d, d_sum += a[i].d;
//	sort(a + 1, a + 1 + n, cmp);
//	long long int sum = 0;
//	int t = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		d_sum -= a[i].d;
//		t = 2 * a[i].t;
//		sum += d_sum * t;
//	}
//	cout << sum << endl;
//	return 0;
//}

//确定交换相邻两个目标的顺序 对其余排好序的结果没有影响 即可根据这两个目标交换前后的结果 确定排序规则
//P1012 贪心排序模板题
//const int N = 30;
//string a[N];
//int n;
//bool cmp(string& x, string& y)
//{
//	string s1 = x + y;
//	string s2 = y + x;
//	return s1 > s2;
//}
//int main()
//{
//	cin >> n;
//	string s;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	sort(a + 1, a + 1 + n, cmp);
//	for (int i = 1; i <= n; i++)s += a[i];
//	cout << s << endl;
//	return 0;
//}